package com.practice.niuke.new_direct_basics.class12;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 在数组中想找到一个数， 左边和右边比这个数小、 且离这个数最近的位置。
 * 如果对每一个数都想求这样的信息， 能不能整体代价达到O(N)？ 需要使用到单调栈结构
 * 单调栈结构的原理和实现
 */
public class Code02_MonotonousStack {

	// 给定一个arr，i -> arr[i]
	// 返回的结果
	// int[][]  i*2 含义：
	// [
	//    [0],[1]  长度为2
	//    [0],[1]  长度为2
	//    [0],[1]  长度为2
	// ]
	// res[i][0]  i位置的数，左边离i最近，比i小的数，位置是啥
	// res[i][1]  i位置的数，右边离i最近，比i小的数，位置是啥
	public static int[][] getNearLessNoRepeat(int[] arr) {
		int[][] res = new int[arr.length][2];
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < arr.length; i++) { // i -> arr[i]
			while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
				// 当前弹出的东西 ： popIndex  -> arr[popIndex]
				int popIndex = stack.pop();
				int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
				res[popIndex][0] = leftLessIndex;
				res[popIndex][1] = i;
			}
			stack.push(i);
		}
		while (!stack.isEmpty()) {
			int popIndex = stack.pop();
			int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
			res[popIndex][0] = leftLessIndex;
			res[popIndex][1] = -1;
		}
		return res;
	}

	// arr可以无重复值，也可以有重复值
	// 返回的结果
	// arr = {3,1,2}
	//        0 1 2
	//  [
	//    [-1,1]
	//    [-1,-1]
	//    [1,-1]
	//  ]
	//
	// int[][]  N*2 含义：
	// [
	//   0: [0],[1]  长度为2
	//    [0],[1]  长度为2
	//    [0],[1]  长度为2
	// ]
	// res[i][0]  i位置的数，左边离i最近，比arr[i]小的数，位置是啥
	// res[i][1]  i位置的数，右边离i最近，比arr[i]小的数，位置是啥
	public static int[][] getNearLess(int[] arr) {
		int N = arr.length;
		int[][] res = new int[N][2];
		// 准备一个栈，栈里面放List，每个List是一群位置，
		// List<Integer> -> 放的是位置， 同样值的东西，位置压在一起
		Stack<  List<Integer>  > stack = new Stack<>();
		for (int i = 0; i < arr.length; i++) {  // i -> arr[i]进栈
			// 底 -> 顶， 小 -> 大
			while (
					// 栈不为空
					!stack.isEmpty()
							&&
							// 栈顶位置的元素所代表的原数组的值 > 当前位置所代表的原数组的值
							arr[stack.peek().get(0)] > arr[i]
			) {
				// 弹出栈顶元素
				List<Integer> popIs = stack.pop();
				// 取位于下面位置的列表中，最晚加入的那个（列表末尾）
				int leftLessIndex = stack.isEmpty() ? -1 : stack.peek()
						.get(stack.peek().size() - 1);
				for (Integer popi : popIs) {
					res[popi][0] = leftLessIndex;
					res[popi][1] = i;
				}
			}
			// i位置要进栈
			if (
				// 栈不为空
					!stack.isEmpty()
							&&
							// 栈顶位置的元素所代表的原数组的值 = 当前位置所代表的原数组的值
							arr[stack.peek().get(0)] == arr[i]
			) {
				// 将当前位置加入到栈顶列表的末尾
				stack.peek().add(i);
			} else { // arr[i]一定大于当前栈顶列表的代表数字，或者栈为空
				ArrayList<Integer> list = new ArrayList<>();
				list.add(i);
				stack.push(list);
			}
		}
		// 遍历结束了，单独处理栈中的元素
		while (!stack.isEmpty()) {
			List<Integer> popIs = stack.pop();
			// 取位于下面位置的列表中，最晚加入的那个（列表末尾）
			int leftLessIndex = stack.isEmpty() ? -1 : stack.peek()
					.get(stack.peek().size() - 1);
			for (Integer popi : popIs) {
				res[popi][0] = leftLessIndex;
				res[popi][1] = -1;
			}
		}
		return res;
	}

	// for test
	public static int[] getRandomArrayNoRepeat(int size) {
		int[] arr = new int[(int) (Math.random() * size) + 1];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = i;
		}
		for (int i = 0; i < arr.length; i++) {
			int swapIndex = (int) (Math.random() * arr.length);
			int tmp = arr[swapIndex];
			arr[swapIndex] = arr[i];
			arr[i] = tmp;
		}
		return arr;
	}

	// for test
	public static int[] getRandomArray(int size, int max) {
		int[] arr = new int[(int) (Math.random() * size) + 1];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) (Math.random() * max) - (int) (Math.random() * max);
		}
		return arr;
	}

	// for test
	public static int[][] rightWay(int[] arr) {
		int[][] res = new int[arr.length][2];
		for (int i = 0; i < arr.length; i++) {
			int leftLessIndex = -1;
			int rightLessIndex = -1;
			int cur = i - 1;
			while (cur >= 0) {
				if (arr[cur] < arr[i]) {
					leftLessIndex = cur;
					break;
				}
				cur--;
			}
			cur = i + 1;
			while (cur < arr.length) {
				if (arr[cur] < arr[i]) {
					rightLessIndex = cur;
					break;
				}
				cur++;
			}
			res[i][0] = leftLessIndex;
			res[i][1] = rightLessIndex;
		}
		return res;
	}

	// for test
	public static boolean isEqual(int[][] res1, int[][] res2) {
		if (res1.length != res2.length) {
			return false;
		}
		for (int i = 0; i < res1.length; i++) {
			if (res1[i][0] != res2[i][0] || res1[i][1] != res2[i][1]) {
				return false;
			}
		}

		return true;
	}

	// for test
	public static void printArray(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int size = 10;
		int max = 20;
		int testTimes = 2000000;
		for (int i = 0; i < testTimes; i++) {
			int[] arr1 = getRandomArrayNoRepeat(size);
			int[] arr2 = getRandomArray(size, max);
			if (!isEqual(getNearLessNoRepeat(arr1), rightWay(arr1))) {
				System.out.println("Oops!");
				printArray(arr1);
				break;
			}
			if (!isEqual(getNearLess(arr2), rightWay(arr2))) {
				System.out.println("Oops!");
				printArray(arr2);
				break;
			}
		}
	}
}
